package org.example.myleet.p525;

import java.util.HashMap;
import java.util.Map;

/**
 * 前缀和 + 哈希表
 */
public class Solution {
    public int findMaxLength(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            nums[i] = nums[i] == 0 ? -1 : 1;
        }
        int[] preSum = new int[nums.length];
        preSum[0] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            preSum[i] = preSum[i - 1] + nums[i];
        }
        int result = 0;
        Map<Integer, Integer> sumIndexMap = new HashMap<>();
        sumIndexMap.put(0, -1);
        for (int i = 0; i < preSum.length; ++i) {
            if (sumIndexMap.containsKey(preSum[i])) {
                result = Math.max(result, i - sumIndexMap.get(preSum[i]));
            } else {
                sumIndexMap.put(preSum[i], i);
            }
        }
        return result;
    }
}
